package com.ctl.algorithm;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

//给你一个字符串 s，找到 s 中最长的回文子串。
//
//示例 1：
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//示例 2：
//
//输入：s = "cbbd"
//输出："bb"
//示例 3：
//
//输入：s = "a"
//输出："a"
//示例 4：
//
//输入：s = "ac"
//输出："a"
public class AbccbA {
    public static void main(String[] args) {
        String str = "baabaad";
//        str = "abcabcbb";
//        str = "baa";
        Map<String, Integer> map = new HashMap<>();
        map.put(String.valueOf(str.charAt(0)), 1);
        int length = str.length();
        Queue<String> characterQueueLeft = new LinkedList();
        Queue<String> characterQueueRight = new LinkedList();
        for (int i = 0; i < str.length(); i++) {
            characterQueueLeft.clear();
            characterQueueRight.clear();
            int cur = i;
            int left = cur;
            int right = length - cur - 1;
            int min = Math.min(left, right);
//            System.out.println(left + "\t\t\t" + cur + "\t\t\t" + right + "\t\t\t" + str.charAt(cur) + "\t\t\t" + min);
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append(str.charAt(cur));
            for (int j = 1; j <= min; j++) {
                if (str.charAt(cur - j) == str.charAt(cur + j)) {
                    stringBuilder.append(str.charAt(cur - j));
                    stringBuilder.insert(0, str.charAt(cur - j));
                } else {
                    break;
                }
            }
            if (stringBuilder.length() > 0 && !map.values().contains(stringBuilder.length())) {
                map.put(stringBuilder.toString(), stringBuilder.length());
            }            //String str="babad";
            left = cur - 1;
            right = length - cur;
            min = Math.min(left, right);
            stringBuilder = new StringBuilder();
            for (int j = 1; j <= min; j++) {
                char cl = str.charAt(cur - j);
                char cr = str.charAt(cur - 1 + j);
                if (cl == cr) {
                    stringBuilder.append(str.charAt(cur - j));
                    stringBuilder.insert(0, str.charAt(cur - j));
                } else {
                    break;
                }
            }
            if (stringBuilder.length() > 0 && !map.values().contains(stringBuilder.length())) {
                map.put(stringBuilder.toString(), stringBuilder.length());
            }
            characterQueueLeft.clear();
            characterQueueRight.clear();
            left = cur;
            right = length - cur - 1;
            String leftStr = str.substring(0, cur);
            String rightStr = str.substring(cur, length);
            String[] lA = leftStr.split("");
            String[] rA = rightStr.split("");
            for (int i1 = 0; i1 < lA.length; i1++) {
                characterQueueLeft.add(lA[i1]);
            }
            for (int i1 = 0; i1 < rA.length; i1++) {
                characterQueueRight.add(rA[i1]);
            }
            stringBuilder = new StringBuilder();

            min = Math.min(left, right + 1);
            for (int j = 0; j < min; j++) {
                String lStr = ((LinkedList<String>) characterQueueLeft).pollLast();
                String rStr = ((LinkedList<String>) characterQueueRight).pollFirst();
                if (lStr.equals(rStr)) {
                    stringBuilder.append(lStr);
                } else {
                    break;
                }
            }
            String le = stringBuilder.toString();
            String ri = stringBuilder.reverse().toString();
            if (stringBuilder.length() > 0 && !map.values().contains((ri + le).length())) {
                map.put(ri + le, (ri + le).length());
                System.err.println(ri + le);
            }
        }
        System.out.println(map);
    }
}
